package Aleehot100;

/**
 * ClassName: c073
 * Package: Aleehot100
 * Description: 84. 柱状图中最大的矩形
 *
 * @Author BCXJ
 * @Create 2025/8/17 16:38
 * @Version 1.0
 * @Since 1.0
 */
public class c073 {
    public static void main(String[] args) {

    }

    static int r = 0, MAXLEN = 100001;
    static int[] stack = new int[MAXLEN];
    static int n;

    // 纯单调栈的题目
    public static int largestRectangleArea(int[] heights) {
        r = 0;
        int popIndex, l, n = heights.length;
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            while(r > 0 && heights[stack[r - 1]] >= heights[i]) {
                popIndex = stack[-- r];
                l = r == 0 ? -1 : stack[r - 1];
                res = Math.max(res, heights[popIndex] * (i - l - 1));
            }
            stack[r ++] = i;
        }

        // 此时遍历完，但是栈还有数据
        while(r > 0) {
            popIndex = stack[ --r];
            l = r == 0 ? -1 : stack[r - 1];
            res = Math.max(res, heights[popIndex] * (n - l - 1));
        }

        // 返回结果
        return res;
    }


    /*
        static int r = 0, MAXLEN = 100001;
    static int[] stack = new int[MAXLEN];
    static int[][] res = new int[MAXLEN][2];
    static int n;

    public static int largestRectangleArea(int[] heights) {
        int pop, l;
        r = 0;
        int ans = 0;
        n = heights.length;
        // 单调栈 计算
        for (int i = 0; i < n; i++) {
            while (r > 0 && heights[i] <= heights[stack[r - 1]]) {
                pop = stack[--r];
                l = r == 0 ? -1 : stack[r - 1];
                ans = Math.max(ans, heights[pop] * (i - l - 1));
            }
            stack[r++] = i;
        }
        // 处理剩余的栈的内容
        while (r > 0) {
            pop = stack[--r];
            l = r == 0 ? -1 : stack[r - 1];
            ans = Math.max(ans, heights[pop] * (n - l - 1));
        }
        return ans;
    }
     */
}
